package main.java.indi.zyj.c150.dps;

import java.util.Scanner;

/**
        ....S*
        .***..
        .*..*.
        *.***.
        .T....
 */
public class _01_dps {

    static int m, n;
    static boolean[][] visited = new boolean[110][110];
    static String[][] maze = new String[110][110];
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public static boolean In(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    public static boolean Dfs(int x, int y){
        if (maze[x][y].equals("T")){
            return true;
        }
        visited[x][y] = true;
        maze[x][y] = "m";

        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0], nextY = y + dir[i][1];
            if (In(nextX, nextY) && !maze[nextX][nextY].equals("*") && !visited[nextX][nextY]){
                if (Dfs(nextX, nextY)){
                    return true;
                }
            }
        }

//        int nextX = x - 1, nextY = y;
//        if (In(nextX, nextY) && maze[nextX][nextY].equals("*") && !visited[nextX][nextY]){
//            if (Dfs(nextX, nextY)){
//                return true;
//            }
//        }
//
//        nextX = x; nextY = y - 1;
//        if (In(nextX, nextY) && maze[nextX][nextY].equals("*") && !visited[nextX][nextY]){
//            if (Dfs(nextX, nextY)){
//                return true;
//            }
//        }
//
//        nextX = x + 1; nextY = y;
//        if (In(nextX, nextY) && maze[nextX][nextY].equals("*") && !visited[nextX][nextY]){
//            if (Dfs(nextX, nextY)){
//                return true;
//            }
//        }
//
//        nextX = x; nextY = y + 1;
//        if (In(nextX, nextY) && maze[nextX][nextY].equals("*") && !visited[nextX][nextY]){
//            if (Dfs(nextX, nextY)){
//                return true;
//            }
//        }

        visited[x][y] = false;
        maze[x][y] = ".";

        return false;
    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int x = 0;
        int y = 0;

        System.out.println("请输入迷宫的行列数:");
        m = scan.nextInt();
        n = scan.nextInt();

//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                maze[i][j] = scan.nextLine();
//            }
//        }
        for (int i = 0; i <m ; i++) {
            String s=scan.next();
            for (int j = 0; j <n ; j++) {
                maze[i][j] = s.charAt(j) + "";
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (maze[i][j].equals("S")){
                    x = i;
                    y = j;
                }
            }
        }

        if (Dfs(x, y)){
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(maze[i][j]);
                }
                System.out.println();
            }
        }else {
            System.out.println("No!");
        }

    }


}
